package test.solution;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<String> strs = new ArrayList<String>();
        while (n-- > 0) {
            strs.add(scanner.next());
        }
        for (String str : strs) {
            System.out.println(getMaxLen(str));
        }
        scanner.close();
    }

    private static int getMaxLen(String str) {
        char separator = '-';
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(separator);
        for (int i = 0; i < str.length(); i++) {
            stringBuilder.append(str.charAt(i));
            stringBuilder.append(separator);
        }
        String newStr = stringBuilder.toString();
        List<Integer> lens = new ArrayList<Integer>();
        for (int i = 0; i < newStr.length(); i++) {
            int minLen = getMinLen(lens, i);
            int len = getPdLength(newStr, i, minLen);
            lens.add(len);
        }
        int maxLen = 0;
        char cen = separator;
        for (int i = 0; i < lens.size(); i++) {
            int len = lens.get(i);
            if (len > maxLen) {
                maxLen = len;
                cen = newStr.charAt(i);
            } else if (len == maxLen && newStr.charAt(i) != separator) {
                cen = newStr.charAt(i);
            }
        }

        maxLen = maxLen - (maxLen + 1) / 2;
        return maxLen;
    }

    private static int getMinLen(List<Integer> lens, int index) {
        int j = (1 + index) / 2;
        int len = 1;
        for (; j < index; j++) {
            int v = Math.min(lens.get(2 * j - index), lens.get(j) - 2 * (index - j));
            if (v > len) {
                len = v;
            }
        }
        return len;
    }

    private static int getPdLength(String str, int center, int minLength) {
        if (minLength < 1) {
            minLength = 1;
        }
        int start = (minLength + 1) / 2;
        int len = minLength;
        while (center - start >= 0 && center + start < str.length() && str.charAt(center + start) == str.charAt(center - start)) {
            len += 2;
            start += 1;
        }
        return len;
    }


}